Qu'est-ce que crible d'eratosthène ?

Le crible d'Eratosthène est une méthode mathématique pour trouver les nombres premiers jusqu'à un certain nombre donné. Cette méthode a été mise au point par le mathématicien grec Eratosthène au IIIe siècle avant notre ère.

Le principe du crible d'Eratosthène est simple. On commence par écrire tous les nombres de 2 à N (N étant le nombre jusqu'auquel on veut chercher des nombres premiers) sur une feuille de papier. Ensuite, on contemple le premier nombre, qui est 2, et on raye tous les multiples de 2 (qui sont donc tous les nombres pairs supérieurs à 2). Puis, on passe au premier nombre non rayé qui est 3 et on raye tous ses multiples (c'est-à-dire tous les nombres impairs supérieurs à 3). On procède ainsi jusqu'à épuisement des nombres non rayés.

À la fin, tous les nombres qui n'ont pas été rayés sont des nombres premiers. Cette méthode est très efficace car elle élimine rapidement tous les nombres multiples d'un nombre donné, qui ne peuvent donc pas être premiers.

Le crible d'Eratosthène est encore utilisé de nos jours en informatique pour trouver des nombres premiers dans les systèmes de chiffrement cryptographiques.